package com.lcm.algorithm.datatest.dp;

/**
 * @description: 343. 整数拆分
 * 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
 *
 * 示例 1:
 *
 * 输入: 2
 * 输出: 1
 * 解释: 2 = 1 + 1, 1 × 1 = 1。
 * 示例 2:
 *
 * 输入: 10
 * 输出: 36
 * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
 * 说明: 你可以假设 n 不小于 2 且不大于 58。
 * @author: lcm
 * @create: 2020-04-07 09:56
 **/

public class IntegerBreak {

    public static void main(String[] args){
        System.out.println(integerBreak2(2));
        System.out.println(integerBreak2(10));
        System.out.println(integerBreak2(30));

        System.out.println(integerBreak1(2));
        System.out.println(integerBreak1(10));
        System.out.println(integerBreak1(30));
    }

    /**
     * 1.暴力
     * @param n
     * @return
     */
    public static int integerBreak1(int n) {
        if(n==2) return 1;
        int result=-1;
        for(int i=1;i<n;i++){
            result=Math.max(result,Math.max(i*(n-i),integerBreak1(n-i)*i));
        }
        return result;
    }

    /**
     * 2.动态规划，记录子问题解
     * @param n
     * @return
     */
    public static int integerBreak2(int n) {
        int[] array=new int[n+1];
        array[1]=1;
        for(int i=2;i<=n;i++){
            array[i]=-1;
            for(int j=1;j<i;j++){
                array[i]=Math.max(array[i],Math.max(j*(i-j),j*array[i-j]));
            }
        }
        return array[n];
    }

}
